class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        // 这里进行空间复杂度的优化
        int n = triangle.size();
        vector<int> dp(n + 1, 0x3f3f3f3f);
        dp[1] = 0;
        int ret = 0x3f3f3f3f;
        for(int i = 1; i <= n; i++)
        {
            int prev = dp[1];
            for(int j = 1; j <= i; j++)
            {
                int t = dp[j];
                dp[j] = min(dp[j], prev) + triangle[i - 1][j - 1];
                prev = t;
                if(i == n)
                    ret = min(ret, dp[j]);
            }
        }
        return ret;


        // 下面的解法空间复杂度是O(N^2)的
        // int n = triangle.size();
        // vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x3f3f3f3f));
        // dp[0][0] = 0;
        // int ret = 0x3f3f3f3f;
        // for(int i = 1; i <= n; i++)
        // {
        //     for(int j = 1; j <= i; j++)
        //     {
        //         dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i - 1][j - 1];
        //         if(i == n)
        //             ret = min(ret, dp[i][j]);
        //     }
        // }
        // return ret;
    }
};